import Foundation

/**
 剑指 Offer 04. 二维数组中的查找
 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 
 */

// 竖向先比较，大于目标，换另一个行
//func findNumberIn2DArray(_ matrix: [[Int]], _ target: Int) -> Bool {
//    for nums in matrix {
//        for value in nums {
//            // i j 对应的值
//
//            if value > target {
//                // 大于目标值，退出当前循环
//                break
//            } else if value == target {
//                return true
//            }
//        }
//    }
//    return false
//}

func findNumberIn2DArray(_ matrix: [[Int]], _ target: Int) -> Bool {
    let rowMax = matrix.count
    let columnMax = matrix.first?.count ?? 0
    
    var row = rowMax - 1, column = 0
    
    while row >= 0 && column < columnMax {
        if matrix[row][column] == target {
            return true
        } else if matrix[row][column] > target {
            row -= 1
        } else {
            column += 1
        }
    }
    return false
}

let nums = [[1,   4,  7, 11, 15],
            [2,   5,  8, 12, 19],
            [3,   6,  9, 16, 22],
            [10, 13, 14, 17, 24],
            [18, 21, 23, 26, 30]]

findNumberIn2DArray(nums, 5)
findNumberIn2DArray(nums, 20)


// *************************************************

// 8ms
func replaceSpace0(_ s: String) -> String {
    return s.replacingOccurrences(of: " ", with: "%20")
}

// 0ms 哈哈
func replaceSpace(_ s: String) -> String {
    var str = ""
    for char in s {
        if char == " " {
            str += "%20"
        } else {
            str += String(char)
        }
    }
    return str
}

replaceSpace("We are happy.")
